package com.hy.diff_array;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:差分数组
 * 差分数组（Differences Array）是一种用于高效处理数组元素修改操作的数据结构。它的主要作用是在原始数组中进行元素的增减操作，
 * 以便快速地获取修改后的数组。
 *
 * 差分数组的构建方式如下：
 * 1、初始化一个与原始数组相同大小的差分数组，初始值全部设置为0。
 * 2、对于原始数组的某个区间（通常是一个连续的子数组），增加或减少一个值。这个操作会反映在差分数组中的两个位置上：区间的起始位置和区间的下一个位置。
 * 区间起始位置的差分数组值增加，而区间的下一个位置的差分数组值减少。
 *
 *
 * 应用场景：差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。
 * User:Mr.Du
 * Date:2023/9/26
 * Time:00:15
 */
public class DiffArrayTemplate {

    private int[] diff;

    //1、初始化差分数组，diff[i] 就是 nums[i] 和 nums[i-1] 之差：
    public DiffArrayTemplate(int[] nums){
        diff = new int[nums.length];
        diff[0] = nums[0];
        for(int i = 1;i < nums.length;i++){
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    // 3、加减操作(val值可以为正/负)
    // diff[i] += val 意味着给 nums[i..] 所有的元素都加了val，然后 diff[j+1] -= val 又意味着对于 nums[j+1..] 所有元素再减val，
    // 那综合起来，是不是就是对 nums[i..j] 中的所有元素都加val了
    public void increment(int start, int end, int val){
        diff[start] += val;
        if(end + 1 < diff.length){
            diff[end + 1] -= val;
        }
    }

    // 2、通过这个 diff 差分数组是可以反推出原始数组 nums 的
    public int[] result(){
        int[] res = new int[diff.length];
        res[0] = diff[0];
        for(int i = 1;i < diff.length;i++){
            // 这一步其实就是把第一步的等式变了个型
            res[i] = diff[i] + res[i - 1];
        }
        return res;
    }
}
